// 给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

// 示例 1:

// 输入: 2
// 输出: [0,1,1]

//一个数比如a，如果是偶数，那么a比特位1的个数和(a/2)比特位1的个数是一样的，因为一个数是偶数那么他的二进制比他的一半的二进制只是多了一个0而已。

// 如果是奇数就不一样了，他会比除以2的结果多了一个1（比如9的二进制比4的二进制多一个1，19的二进制比9的二进制多一个1，等等）。

class Solution {
    public int[] countBits(int num) {
        int[] bits = new int[num + 1];
        for (int i = 1; i <= num; i++) {
            //一个数的比特位1的个数先让他等于他一半的比特位量
            bits[i] = bits[i / 2];
            //如果是奇数还要加1
            if ((i & 1) == 1)
                bits[i]++;
        }
        return bits;
    }
}
